/** --------------- 开放定址法 --------------- */

class HashTable {
  cnt = 0; // 存入了多少个值
  data = []; // 存string的data
  flags = []; // 标记数组，当前位置是否有过值

  constructor(n = 100) { // n: 数组的长度，中途不可以随意修改
    this.flags = new Array(n).fill(false);
    this.data = new Array(n);
  }
  /** 插入值 */
  insert(s) {
    let index = this.hash_func(s) % this.data.length; // get hash code
    index = this.recalc_ind(index, s);
    if (this.flags[index] == false) {
      this.data[index] = s;
      this.flags[index] = true;
      this.cnt++;
      if (this.cnt * 100 > this.data.length * 75) { // 这里如果存满75%，进行扩容
        this.expand()
      }
    }
    return;
  }
  /** 扩容
   * 注意我们不能随意的修改数组长度，因为这里取的下标是基于this.date.length的（取余），一旦修改了，就会很麻烦
   * 这的思路是创建一个两倍长度的数组。用来扩容。但是需要把每一个值转换放到新的数组中去。因为长度不同，所以index下标也是不同的，他们之间不是一个简单的拷贝关系。
   * 所以：我们使用延迟拷贝。
   * 1.插入（insert）的时候在新的数组中插入
   * 2.查找（find）的时候，先find第一个数组。如果找到了值，把小数组中的值放到大数组中去，并且删掉小数组中的值。
   * 这样小数组越来越小、大数组越来越大
   */
  expand() {
    // 简单处理，不做延迟拷贝
    const n = this.data.length * 2;
    const h = new HashTable(n);
    for(var i = 0; i < this.data.length; i ++) {
      if (this.flags[i] == false) continue;
      h.insert(data[i])
    }
    this.flags = h.flags;
    this.data = h.data;
    
  }
  /** 判断有没有 */
  find(s) {
    let index = this.hash_func(s) % this.data.length;
    index = this.recalc_ind(index, s);
    return this.flags[index];
  }
  /**
   * 字符串转换成数字(可以不关心这里是怎么实现的)
   * 比较随意的方法
   * 里面的seed保证是一个素数就可以了(不是也可以)
  */
  hash_func(s) {
    let seed = 131, hash = 0;
    for (var i = 0; s[i]; i++) {
      hash = hash * seed + s[i].charCodeAt();
    }
    return hash & 0x7fffffff; // 为了避免是负数
  }
  /** 处理冲突，如果index已经有值，往后查找 */
  recalc_ind(index, s) {
    let t = 1;
    let tempIndex = index;
    while(this.flags[tempIndex] == true && this.data[tempIndex] != s) {
      index += t * t;
      t += 1;
      tempIndex %= this.data.length; 
    }
    return tempIndex;
  }
}

const ht = new HashTable();
ht.insert("abc");
ht.insert("bbb");
ht.find("bbb")
ht.find("abc");
ht.find("dafj")


// ----------------------   链式地址法   -----------------------------
